#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    string intToRoman(int num) {
        // 准备好数值到罗马数字的映射，按从大到小排序
        // 使用 vector 存储 pair，因为它可以保持插入顺序
        vector<pair<int, string>> valueSymbols = {
            {1000, "M"},
            {900,  "CM"},
            {500,  "D"},
            {400,  "CD"},
            {100,  "C"},
            {90,   "XC"},
            {50,   "L"},
            {40,   "XL"},
            {10,   "X"},
            {9,    "IX"},
            {5,    "V"},
            {4,    "IV"},
            {1,    "I"}
        };

        string roman;

        // 遍历映射表
        for (const auto& pair : valueSymbols) {
            int value = pair.first;
            string symbol = pair.second;

            // 尽可能多地从 num 中减去当前 value，并追加对应的 symbol
            while (num >= value) {
                roman += symbol;
                num -= value;
            }

            // 如果 num 已经为 0，可以提前结束循环
            if (num == 0) {
                break;
            }
        }

        return roman;
    }
};